// 138.随机链表的复制
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        // 通过将每一个位置的节点拷贝一份放到每一个节点的后面
        Node* cur = head;
        while(cur)
        {
            Node* newnode = new Node(cur->val);
            newnode->next = cur->next;
            cur->next = newnode;
            cur = newnode->next;
        }
        // 此时每个节点都被拷贝了一份
        // 对随机指针进行修改
        cur = head;
        while(cur)
        {
            Node* copy = cur->next;
            copy->random = ( cur->random ? cur->random->next : nullptr);
            cur = copy->next;
        }
        //  将拷贝节点取下来
        Node *phead = new Node(0) , *tail = phead;
        cur = head;
        while(cur)
        {
            tail->next = cur->next;
            tail = tail->next;
            cur->next = tail->next;         // 恢复原链表的状态
            cur = cur->next;
        }
        Node* ret = phead->next;
        delete phead;
        return ret;
    }
};